/*
 * @lc app=leetcode.cn id=518 lang=typescript
 *
 * [518] 零钱兑换 II
 */

// @lc code=start
function change(amount: number, coins: number[]): number {
  const n = coins.length;

  // dp[i]表示金额之和等于i的方案数量
  const dp = new Array(amount + 1).fill(0);
  // 金额之和位0的方案数就是不选择任何金币这一种方案
  dp[0] = 1;

  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] += dp[i - coin];
    }
  }

  return dp[amount];
}
// @lc code=end
